package other;



/**
 * @author heran
 * @since 2020/6/20 5:23 下午
 */
public class KMP {
    /**
     * 查子串
     *
     * @param haystack 原始文本
     * @param needle   子串
     * @return 子串位置
     */
    public int strStr(String haystack, String needle) {
        if (needle.length() > haystack.length()) return -1;
        int[] next = buildNext(needle);
        int n = haystack.length(), m = needle.length(), i = 0, j = 0;
        while (i < n && j < m) {
            if (j < 0 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j != m) return -1;
        return i - j;
    }


    /**
     * 构建Next数组
     *
     * @param s 字符串
     * @return Next数组
     */
    public int[] buildNext(String s) {
        int[] next = new int[s.length()];
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            int k = next[i - 1];
            while (s.charAt(k) != s.charAt(i) && k != 0) {
                k = next[k - 1];
            }
            if (s.charAt(k) == s.charAt(i)) {
                next[i] = k + 1;
            } else {
                next[i] = 0;
            }
        }
        for (int i = next.length - 1; i > 0; i--) {
            next[i] = next[i - 1];
        }
        next[0] = -1;
        return next;
    }

    public static void main(String[] args) {
        String s = "actgpacy";
        KMP kmp = new KMP();
        System.out.println(kmp.strStr(s, "t"));
    }
}
